package leetcode.editor.vscdev.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class lc47 {
    /* 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。 */
    public static void main(String[] args) {
        
    }
}
// 个人想法：首先对nums进行排序，然后结合上一题即可
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used; // 使用used数组标记使用过的元素
    public List<List<Integer>> permute(int[] nums) {
        if (nums == null || nums.length == 0) return result;
        used = new boolean[nums.length];
        Arrays.sort(nums);
        backtracking(nums);
        return result;
    }
    private void backtracking(int[] nums){
        if(path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i - 1])) {
                continue;// 如果当前元素被使用过，则跳过
            }
            used[i] = true; // 标记使用过
            path.add(nums[i]);
            backtracking(nums);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}